|
In number theory, Euler's totient function (or Euler's phi function), denoted as or , is an arithmetic function that counts the positive integers less than or equal to ''n'' that are relatively prime to ''n''. (These integers are sometimes referred to as totatives of ''n''.) Thus, if ''n'' is a positive integer, then is the number of integers ''k'' in the range for which the greatest common divisor . Euler's totient function is a multiplicative function, meaning that if two numbers ''m'' and ''n'' are coprime, then . For example, let . Then and . The other six numbers in the range , that is 1, 2, 4, 5, 7 and 8 are relatively prime to 9. Therefore, . As another example, since . Euler's phi function is important mainly because it gives the order of the multiplicative group of integers modulo ''n'' (the group of units of the ring ℤ/nℤ).〔See Euler's theorem.〕 It also plays a key role in the definition of the RSA encryption system. == History, terminology, and notation == Leonhard Euler introduced the function in 1763.〔L. Euler "(Theoremata arithmetica nova methodo demonstrata )" (An arithmetic theorem proved by a new method), ''Novi commentarii academiae scientiarum imperialis Petropolitanae'' (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), 8 (1763), 74-104. (The work was presented at the Saint-Petersburg Academy on October 15, 1759. A work with the same title was presented at the Berlin Academy on June 8, 1758). Available on-line in: Ferdinand Rudio, , ''Leonhardi Euleri Commentationes Arithmeticae'', volume 1, in: ''Leonhardi Euleri Opera Omnia'', series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), (pages 531-555 ). On page 531, Euler defines ''n'' as the number of integers that are smaller than ''N'' and relatively prime to ''N'' (… aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, …), which is the phi function, φ(N).〕〔Sandifer, p. 203〕〔Graham et al. p. 133 note 111〕 However, he did not at that time choose any specific symbol to denote it. In a 1784 publication, Euler studied the function further, choosing the Greek letter π to denote it: he wrote πD for "the multitude of numbers less than D, and which have no common divisor with it".〔L. Euler, ''(Speculationes circa quasdam insignes proprietates numerorum )'', Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18-30, or Opera Omnia, Series 1, volume 4, pp. 105-115. (The work was presented at the Saint-Petersburg Academy on October 9, 1775).〕 The standard notation〔〔Both and are seen in the literature. These are two forms of the lower-case Greek letter phi.〕 φ(''A'') comes from Gauss's 1801 treatise ''Disquisitiones Arithmeticae''.〔Gauss, ''Disquisitiones Arithmeticae'' article 38〕 However, Gauss didn't use parentheses around the argument and wrote φ''A''. Thus, it is often called Euler's phi function or simply the phi function. In 1879, J. J. Sylvester coined the term totient for this function,〔J. J. Sylvester (1879) "On certain ternary cubic-form equations", ''American Journal of Mathematics'', 2 : 357-393; Sylvester coins the term "totient" on (page 361 ).〕 so it is also referred to as Euler's totient function, the Euler totient, or Euler's totient. Jordan's totient is a generalization of Euler's. The cototient of ''n'' is defined as ''n'' – φ(''n''), i.e. the number of positive integers less than or equal to ''n'' that are divisible by at least one prime that also divides ''n''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Euler's totient function」の詳細全文を読む スポンサード リンク
|